The present invention relates to the field of data processing systems and specifically to the field of dividers and methods for dividing within data processing systems.
Prior art data processing systems usually require divisions of numbers using either fixed point or floating point arithmetic.
Prior art methods and apparatus for performing divisions typically employ combinations of adders and other functional units rather than employing a single dedicated divide apparatus. In such methods and apparatus, the quotient is calculated from a given divisor and a given dividend using an iterative process requiring many cycles of the system.
In order to increase the speed of divisional computations in data processing systems, specially selected division algorithms and circuits are frequently employed. Typical division algorithms rely upon sequences including both addition and subtraction steps. Such division algorithms can be characterized as either restoring or non-restoring. In restoring algorithms, typically the divisor is repeatedly subtracted in successive cycles from portions of the dividend to form successive partial remainders. When the partial remainder changes from positive to negative, the negative partial remainder is restored to the previous positive value that existed prior to the last subtraction of the divisor. Each time a subtraction occurs, a portion of the quotient is formed. Additional portions of the dividend together with the last-formed partial remainder are processed in the same way until the entire quotient and the final remainder have been formed.
In other algorithms, the step of having to restore the partial remainder is avoided. One such algorithm is described in U.S. Pat. No. 3,828,175 entitled METHOD AND APPARATUS FOR DIVISION EMPLOYING TABLE-LOOKUP AND FUNCTIONAL ITERATION.
Other algorithms, called non-restoring algorithms, form negative partial remainders but still avoid extra time for restoration of partial remainders. In an example where an addition or subtraction computation takes one cycle and where restoration is required one-half of the time, non-restoring division requires one cycle per bit and restoring division requires one and one-half cycles per bit. Hence, a 56-bit division would require 56 cycles using non-restoring division or 84 cycles using restoring division. This example indicates that restoring division takes more time and therefore is undesirable for high-speed operation. The speed of executing a non-restoring division is often increased if the divisor is normalized. When the leading bits of the partial remainder are strings of zeros (if positive) or ones (if negative), it is known that the result of a divisor subtraction (addition) will be negative (positive) without having to actually perform the subtraction. Therefore, subtraction for such leading strings may be skipped to enhance performance of the division algorithm. In general, there is no advantage to skipping strings having a length of one bit as compared to proceeding without such skipping. The advantage of skipping strings of length over four bits is not great because such strings statistically occur infrequently. Assuming for purpose of explanation, that bits in a partial remainder are 0 or 1 at random and assuming that skipping is restricted to strings of lengths of two, three and four bits, a typical division algorithm will proceed at 16/23 cycles per bit so that 56-bit divisions will take, on an average, approximately 39 cycles. This example indicates why normalization (skipping of strings of leading 0's or 1's) has been effective in the prior art to reduce the time required for division computation.
While normalization can be effective for reducing computational time, no advantage is obtained if the time required for normalization is excessive. Since normalization is usually achieved by shifting, generally a high-speed shifting capability is required to make the normalization effective. Such a capability, of course, requires additional hardware expense. Further complexity exists since the control structure for shifting must include at least a 3-way branch selecting among an add, subtract and shift.
Improved division circuits have been employed using cellular arrays. The term "cellular" implies constructing a circuit from many copies of the same cell. With cellular division circuits, steps of the basic division algorithms are performed in one cycle without need for latching data within the cycle. In typical circuits, partial remainders are kept in "carry-save" form without need to propagate the carries. Prior art cellular division circuits have been based upon both restoring and non-restoring algorithms.
Prior art cellular division circuits have not, in general, been entirely satisfactory either because of excessive hardware cost or because the computational speed is too slow.
In view of the above background, it is an objective of the present invention to provide an improved division circuit and method for use in a data processing system.